package com.code.leetcode._202507;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 46 全排列
public class Permute {
    /**
     * 给一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
     * 示例1：输入：nums=[1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     * 示例2：nums=[0,1]
     * 输出：[0,1],[1,0]]
     * 示例3:nums=[1]
     * 输出：[[1]]
     **/
    public static void main(String[] args) {
        Permute p = new Permute();
        System.out.println(p.permute(new int[]{1,2,3}));
    }

    /**
     * 回溯法：一种通过探索所有可能的候选解来找出所有的解的算法，如果候选被确认不是一个叫解
     * （或者至少不是最后一个解），回溯算法会通过上一步进行一些变化抛弃该解，即回溯并且再次尝试。
     * 这个问题其实可以看作n个排列成一行的空格，我们需要从左往右依次填入题目给定的n个数，每个数只能使用一次。
     * 那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依次尝试填入一个数，看能不能填完这n个空格，
     * 在程序中我们可以用 回溯法 来模拟这个过程
     * 我们定义递归函数backtrack(first,output)表示从左到右填到第first个位置，当前排列为output。那么整个递归
     * 函数分为两个情况：
     * 1、如果first=n，说明我们已经填完了n个位置(注意下标从0开始),找到一个可行的解。我们将output放入答案组中，递归结束。
     * 2、如果first<n，我们要考虑这个第first个位置我们要填哪个数。根据题意要求我们肯定不能填我们已经填过的数，因此很容易想到
     * 的一个处理手段时我们定义一个标记数组uis来标记已经填过的数，那么在填第first个数的时候我们遍历题目给定的n个数，
     * 如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数backtrace(first+1,output)。
     * 回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。
     * 使用标记数组来处理填过的数时一个很直观的思路，但是可不可以去掉这个标记数组呢？毕竟标记数组也增加了我们算法的空间复杂度。
     * 答案时可以的，我们可以将题目给定的n个数的数组nums划分为左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们
     * 在回溯的时候只要动态维护这个数组即可。
     * 具体来说，假设我们已经填到第first个位置，那么nums数组中[0,first-1]是已经填过的数的集合，[first,n-1]是待填的数
     * 的集合。我们肯定是尝试用[first,n-1]里的数去填第first个数，假设待填的数的下标为i，那么填完以后我们将第i个数和
     * 第first个数交换，即能使的在填第first+1个数的时候nums数组的[0,first]部分为已填过的数，[first+,n-1]为待填的数，
     * 回溯的时候交换回来即能完成撤销操作。
     * 举个简单的例子，假设我们有[2,5,8,9,10]这5个数要填入，已经填带第3个位置，已经填了[8,9]两个数，那么这个数组
     * 目前为[8,9|2,5,10]这样的状态，分割符区分了左右两个部分。假设这个位置我们要填10个数，为了维护数组，我们将2和10
     * 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填[8,9,10|2,5]
     * 当然善于思考的读者肯定已经发现这样生成的全排列并不是按字典序存储在答案数组中的，如果题目要求按字典序输出，那么请还是
     * 用标记数组或者其他方法。
     **/
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        if (first == n) {
            res.add(new ArrayList<>(output));
        }
        for (int i = first; i < n; i++) {
            Collections.swap(output, first, i);
            backtrack(n, output, res, first + 1);
            Collections.swap(output, first, i);
        }
    }


}
